//package cn.handong.tool.algorithm.BFS;
//
//import java.awt.*;
//import java.util.ArrayList;
//import java.util.LinkedList;
//import java.util.Queue;
//import java.util.Scanner;
//
//public class MazeBfs {
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        System.out.println("请输入宽和高：");
//        int width = sc.nextInt();
//        int height = sc.nextInt();
//        System.out.println("迷宫宽为：" + width + "，高为：" + height);
//        int[][] mazearr = new int[2 * width + 1][2 * height + 1];//动态初始化
//        // mazearr.length 宽            mazearr[0].length) 高
//        for (int i = 0; i < mazearr.length; i++) { //行
//            for (int j = 0; j < mazearr[0].length; j++) {
//                if (i%2==0 || j%2 ==0){
//                    mazearr[i][j] = 1;
//                }
//            }
//        }
//
//        int x = 1;
//        int y = 1;  //起始点
//        Point p = new Point(1,1);
//        ArrayList<Point> list = new ArrayList<>();
//        mazearr[x][y] = 2; //起始点设为已访问路
//        //加入邻墙
//        //list.add(new Point(1,2));
//        //list.add(new Point(2,1));
//        list = addWall(new Point(x,y),list,mazearr);
//
//        int r ;
//        while (!list.isEmpty()){
//            r = (int) (Math.random()*list.size());
//            x = list.get(r).x;
//            y = list.get(r).y;  //墙坐标
//
//            if (mazearr[x-1][y]==0){
//                mazearr[x][y] = 2;
//                mazearr[x-1][y]=2; //空格坐标
//                list = addWall(new Point(x-1,y),list,mazearr);
//
//            }
//            if (mazearr[x+1][y]==0){
//                mazearr[x][y] = 2;
//                mazearr[x+1][y]=2;
//                list = addWall(new Point(x+1,y),list,mazearr);
//
//
//            }
//            if (mazearr[x][y-1]==0){
//                mazearr[x][y] = 2;
//                mazearr[x][y-1]=2;
//                list = addWall(new Point(x,y-1),list,mazearr);
//
//            }
//            if (mazearr[x][y+1]==0){
//                mazearr[x][y] = 2;
//                mazearr[x][y+1]=2;
//                list = addWall(new Point(x,y+1),list,mazearr);
//
//
//            }
//            list.remove(r);
//        }
//
//        System.out.println("生成迷宫图：");
//        for (int i = 0; i < mazearr.length; i++) { //行
//            for (int j = 0; j < mazearr[0].length; j++) {
//
//                if (mazearr[i][j] == 1 ) {
//                    System.out.print(" #");
//                } else {
//                    System.out.print("  ");
//                }
//
//            }
//            System.out.println();
//        }
//
//        //bfs广度优先搜索 寻路
//        //1为墙，   2为路，   4为已访问路
//        Point[][] bookarr = new Point[2 * width + 1][2 * height + 1];  //记录父类节点
//        //起点为1，1     终点为mazearr.length-2，mazearr[0].length-2
//        Queue<Point> queue = new LinkedList<>();   //创建队列
//        Point node = new Point(1,1); //起点
//        queue.offer(node);  //起点加入队列
//        mazearr[1][1]=4;  //标记为4，代表已访问
//        while (!queue.isEmpty()){  //队列为空时 结束
//            node = queue.poll();  //取出队首元素，赋值给node;
//            if(node.x==mazearr.length-2 && node.y== mazearr[0].length-2){  //找到终点
//                break;
//            }else {
//                x=node.x;
//                y=node.y;
//                // 相邻且未访问的点加入队列
//                //判断是否有路 上下左右
//                if(mazearr[x-1][y]==2){
//                    queue.offer(new Point(x-1, y));  //加入队列
//                    mazearr[x-1][y]=4;  //标记为已访问；
//                    bookarr[x-1][y] = new Point(x, y);  //记录相应位置的父节点，用来返回路径
//                }
//                if (mazearr[x+1][y]==2){
//                    queue.offer(new Point(x+1, y));
//                    mazearr[x+1][y]=4;
//                    bookarr[x+1][y] = new Point(x, y);
//                }
//                if (mazearr[x][y-1]==2){
//                    queue.offer(new Point(x, y-1));
//                    mazearr[x][y-1]=4;
//                    bookarr[x][y-1] = new Point(x, y);
//                }
//                if (mazearr[x][y+1]==2){
//                    queue.offer(new Point(x, y+1));
//                    mazearr[x][y+1]=4;
//                    bookarr[x][y+1] = new Point(x, y);
//                }
//            }
//        }
//
//        int step = 0; //记录路径步数；
//        //查找路径
//        while ((node.x!=1 || node.y!=1)){
//            //查找相应位置的父节点
//            node = bookarr[node.x][node.y];
//            mazearr[node.x][node.y] = 5; //相应位置标记为5，代表路径
//            step++;
//        }
//        System.out.println("Bfs路径步数为："+step);
//        System.out.println("Bfs路径：");
//        for (int i = 0; i < mazearr.length; i++) { //行
//            for (int j = 0; j < mazearr[0].length; j++) {
//                if ((i==1&&j==1) || (i==mazearr.length-2&&j==mazearr[0].length-2)){
//                    System.out.print(" @");
//                }else if (mazearr[i][j]==5){
//                    System.out.print(" >");
//                }else if (mazearr[i][j]==1){
//                    System.out.print(" #");
//                }else {
//                    System.out.print("  ");
//                }
//            }
//            System.out.println();
//        }
//
//    }
//    public static ArrayList<Point> addWall(Point p,ArrayList<Point> list,int[][] mazearr){  //添加邻墙
//        int x = p.x;
//        int y = p.y;  //路坐标
//        if (0<x-2 && x-2<mazearr.length){ //上
//            if(mazearr[x-2][y]==0 && mazearr[x-1][y]==1){
//                // 加入邻墙
//                list.add(new Point(x-1,y));
//            }
//        }
//        if (0<x+2 && x+2<mazearr.length){ //
//            if(mazearr[x+2][y]==0 && mazearr[x+1][y]==1){
//                // 加入邻墙
//                list.add(new Point(x+1,y));
//            }
//        }
//
//        if (0<y-2 && y-2<mazearr[0].length){ //
//            if(mazearr[x][y-2]==0 && mazearr[x][y-1]==1){
//                // 加入邻墙
//                list.add(new Point(x,y-1));
//            }
//        }
//        if (0<y+2 && y+2<mazearr[0].length){ //
//            if(mazearr[x][y+2]==0 && mazearr[x][y+1]==1){
//                // 加入邻墙
//                list.add(new Point(x,y+1));
//            }
//        }
//        return list;
//    }
//
//}